import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-22
 * Time: 20:12
 */
public class Day5 {
    //217 - 存在重复元素 - 标记
    public boolean containsDuplicate1(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]){
                return true;
            }
        }
        return false;
    }

    //JAVA - Set自带去重功能
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for(int num : nums){
            if(!set.add(num)){
                return true;
            }
        }
        return false;
    }

    //219.存在重复元素II
    public boolean containsNearbyDuplicate1(int[] nums, int k) {
        Set<Integer> set = new HashSet<Integer>();
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (!set.add(nums[i])){
                j = i;
                break;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == nums[j] && i != j){
                if (Math.abs(i - j) <= k){
                    return true;
                }
            }
        }
        return false;
    }
    //优解
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++) {
            if(set.add(nums[i])) {
                if(set.size() > k) {
                    set.remove(nums[i - k]);
                }
            } else {
                return true;
            }
        }
        return false;
    }

    //228.汇总区间 - 标记
    public List<String> summaryRanges1(int[] nums) {
        List<String> list = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int ret = 0;
            if (i < n - 1 && nums[i] + 1 == nums[i + 1]) {
                ret = nums[i];
                while (i < n - 1 && nums[i] + 1 == nums[i + 1]) {
                    i++;
                }
                list.add(ret + "->" + nums[i]);
            }else{
                list.add(nums[i] + "");
            }
        }
        return list;
    }

    public List<String> summaryRanges(int[] nums) {
        List<String> list = new ArrayList<>();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < nums.length; i++) {
            if (!(i < nums.length - 1 && nums[i] + 1 == nums[i + 1])){
                if (sb.length() > 0){
                    sb.append("->");
                }
                sb.append(nums[i]);
                list.add(sb.toString());
                sb = new StringBuffer();
            }else{
                if (sb.length() == 0){
                    sb.append(nums[i]);
                }
            }
        }
        return list;
    }

    //268.丢失的数字 - 标记
    public int missingNumber1(int[] nums) {
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            ret += nums[i];
        }
        return (nums.length + 1) * (nums.length) / 2 - ret;
    }

    public int missingNumber(int[] nums) {
        int ret = nums.length;
        for (int i = 0; i < nums.length; i++) {
            ret ^= nums[i];
            ret ^= i;
        }
        return ret;
    }

    //283.移动0
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length <= 1){
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length){
            nums[j++] = 0;
        }
    }
}
//303.区域和检索 - 数组不可变
class NumArray1 {

    int[] sums;
    public NumArray1(int[] nums) {
        sums = new int[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0){
            return sums[right];
        }else{
            return sums[right] - sums[left - 1];
        }
    }
}
class NumArray {

    int[] sums;
    public NumArray(int[] nums) {
        sums = new int[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (left == 0){
            return sums[right];
        }else{
            return sums[right] - sums[left - 1];
        }
    }
}